{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Good Triplets in an Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #binary-indexed-tree #segment-tree #array #binary-search #divide-and-conquer #ordered-set #merge-sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树状数组 #线段树 #数组 #二分查找 #分治 #有序集合 #归并排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: goodTriplets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计数组中好三元组数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个下标从 <strong>0</strong>&nbsp;开始且长度为 <code>n</code>&nbsp;的整数数组&nbsp;<code>nums1</code>&nbsp;和&nbsp;<code>nums2</code>&nbsp;，两者都是&nbsp;<code>[0, 1, ..., n - 1]</code>&nbsp;的&nbsp;<strong>排列</strong>&nbsp;。</p>\n",
    "\n",
    "<p><strong>好三元组&nbsp;</strong>指的是&nbsp;<code>3</code>&nbsp;个&nbsp;<strong>互不相同</strong>&nbsp;的值，且它们在数组&nbsp;<code>nums1</code> 和&nbsp;<code>nums2</code>&nbsp;中出现顺序保持一致。换句话说，如果我们将&nbsp;<code>pos1<sub>v</sub></code> 记为值&nbsp;<code>v</code>&nbsp;在&nbsp;<code>nums1</code>&nbsp;中出现的位置，<code>pos2<sub>v</sub></code>&nbsp;为值&nbsp;<code>v</code>&nbsp;在&nbsp;<code>nums2</code>&nbsp;中的位置，那么一个好三元组定义为&nbsp;<code>0 &lt;= x, y, z &lt;= n - 1</code>&nbsp;，且&nbsp;<code>pos1<sub>x</sub> &lt; pos1<sub>y</sub> &lt; pos1<sub>z</sub></code> 和&nbsp;<code>pos2<sub>x</sub> &lt; pos2<sub>y</sub> &lt; pos2<sub>z</sub></code>&nbsp;都成立的&nbsp;<code>(x, y, z)</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回好三元组的 <strong>总数目</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums1 = [2,0,1,3], nums2 = [0,1,2,3]\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>\n",
    "总共有 4 个三元组 (x,y,z) 满足 pos1<sub>x</sub> &lt; pos1<sub>y</sub> &lt; pos1<sub>z&nbsp;</sub>，分别是 (2,0,1) ，(2,0,3) ，(2,1,3) 和 (0,1,3) 。\n",
    "这些三元组中，只有 (0,1,3) 满足 pos2<sub>x</sub> &lt; pos2<sub>y</sub> &lt; pos2<sub>z</sub>&nbsp;。所以只有 1 个好三元组。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums1 = [4,0,1,3,2], nums2 = [4,1,0,2,3]\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>总共有 4 个好三元组 (4,0,3) ，(4,0,2) ，(4,1,3) 和 (4,1,2) 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums1.length == nums2.length</code></li>\n",
    "\t<li><code>3 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums1[i], nums2[i] &lt;= n - 1</code></li>\n",
    "\t<li><code>nums1</code>&nbsp;和&nbsp;<code>nums2</code>&nbsp;是&nbsp;<code>[0, 1, ..., n - 1]</code> 的排列。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-good-triplets-in-an-array](https://leetcode.cn/problems/count-good-triplets-in-an-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-good-triplets-in-an-array](https://leetcode.cn/problems/count-good-triplets-in-an-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,0,1,3]\\n[0,1,2,3]', '[4,0,1,3,2]\\n[4,1,0,2,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        numlen = len(nums1)\n",
    "        newnums = [i for i in range(numlen)]\n",
    "        for i in range(numlen):\n",
    "            newnums[nums1[i]] = i\n",
    "        for i in range(numlen):\n",
    "            nums2[i] = newnums[nums2[i]]\n",
    "        # print(nums2)\n",
    "        treearr = [0 for _ in range(numlen+1)]\n",
    "        def add(index, val):\n",
    "            while index <= numlen:\n",
    "                treearr[index] += val\n",
    "                index += index & (-index)\n",
    "        def getsum(index):\n",
    "            res = 0\n",
    "            while index > 0:\n",
    "                res += treearr[index]\n",
    "                index -= index & (-index)\n",
    "            return res\n",
    "        def getrange(left, right):\n",
    "            return getsum(right+1) - getsum(left)\n",
    "        for i in range(numlen):\n",
    "            add(i+1, 0)\n",
    "        # print(treearr)\n",
    "        ans = 0\n",
    "        for idx, item in enumerate(nums2):\n",
    "            left = getrange(0, item-1)\n",
    "            right = numlen-1-item-(idx-left)\n",
    "            # print(idx, item, left, right)\n",
    "            add(item+1, 1)\n",
    "            ans += left*right\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        from sortedcontainers import SortedList\n",
    "        n = len(nums1)\n",
    "        numMap = [0]*n\n",
    "        for i, v in enumerate(nums1):\n",
    "            numMap[v] = i\n",
    "        passed = SortedList()\n",
    "        result = 0\n",
    "        for handled, x in enumerate(nums2):\n",
    "            v = numMap[x]\n",
    "            less = passed.bisect_left(v)\n",
    "            more = handled - less\n",
    "            passed.add(v)\n",
    "            # handled: less  +    more \n",
    "            # unhandled(n-1-handled): v-less + x\n",
    "            # x = n-1-handled - (v-less) = n - 1 - handled - v + less\n",
    "            result += less*(n-1-handled -v + less)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        p = [0] * n\n",
    "        for i, x in enumerate(nums1):\n",
    "            p[x] = i\n",
    "        ans = 0\n",
    "        s = SortedList()\n",
    "        for i in range(1, n - 1):\n",
    "            s.add(p[nums2[i - 1]])\n",
    "            y = p[nums2[i]]\n",
    "            less = s.bisect_left(y)\n",
    "            ans += less * (n - 1 - y - (i - less))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n=len(nums1)\n",
    "        m=[0]*n\n",
    "        for i,num in enumerate(nums1):\n",
    "            m[num]=i+1\n",
    "        tree=[0]*(n+1)\n",
    "        ans=0\n",
    "        #print([m[num] for num in nums2])\n",
    "        for i,num in enumerate(nums2):\n",
    "            t,less=m[num],0\n",
    "            while t>0:\n",
    "                less+=tree[t]\n",
    "                t-=(t&-t)\n",
    "            #print('@',less, tree)\n",
    "            t=m[num]\n",
    "            while t<=n:\n",
    "                tree[t]+=1\n",
    "                t+=(t&-t)\n",
    "            ans+=less*(n-m[num]-(i-less))\n",
    "            #print('#',ans,less,(n-m[num]-(i-less)), tree, n,m[num])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        N = len(nums1)\n",
    "        p = [0]*N\n",
    "        for i,n in enumerate(nums1):\n",
    "            p[n] = i\n",
    "        \n",
    "        res = 0\n",
    "        s = SortedList()\n",
    "        for i,n in enumerate(nums2):\n",
    "            m = p[n]\n",
    "            less = s.bisect_left(m)\n",
    "            res += less*(N-m-1-(i-less))\n",
    "            s.add(m)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def goodTriplets1(self, nums1: List[int], nums2: List[int]) -> int:\r\n",
    "        n = len(nums1)\r\n",
    "        p = [0] * n\r\n",
    "        for i, x in enumerate(nums1):\r\n",
    "            p[x] = i\r\n",
    "        ans = 0\r\n",
    "        tree = [0] * (n + 1)\r\n",
    "        for i in range(1, n - 1):\r\n",
    "            # 将 p[nums2[i - 1]] + 1 加入树状数组\r\n",
    "            j = p[nums2[i - 1]] + 1\r\n",
    "            while j <= n:\r\n",
    "                tree[j] += 1\r\n",
    "                j += j & -j\r\n",
    "            # 计算 less\r\n",
    "            y, less = p[nums2[i]], 0\r\n",
    "            j = y\r\n",
    "            while j:\r\n",
    "                less += tree[j]\r\n",
    "                j &= j - 1\r\n",
    "            ans += less * (n - 1 - y - (i - less))\r\n",
    "        return ans\r\n",
    "        \r\n",
    "\r\n",
    "\r\n",
    "    # 引入 sortedList\r\n",
    "    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:\r\n",
    "        from sortedcontainers import SortedList\r\n",
    "        n = len(nums1)\r\n",
    "        p = [0] * n\r\n",
    "        for i, x in enumerate(nums1):\r\n",
    "            p[x] = i\r\n",
    "        ans = 0\r\n",
    "        s = SortedList()\r\n",
    "        for i in range(1, n - 1):\r\n",
    "            s.add(p[nums2[i - 1]])\r\n",
    "            y = p[nums2[i]]\r\n",
    "            less = s.bisect_left(y)\r\n",
    "            ans += less * (n - 1 - y - (i - less))\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self,n):\n",
    "        self.tree = [0]*n\n",
    "    def add(self,i,v):\n",
    "        while i < len(self.tree):\n",
    "            self.tree[i] += v\n",
    "            i += i&-i\n",
    "    def count(self,i):\n",
    "        res = 0\n",
    "        while i:\n",
    "            res += self.tree[i]\n",
    "            i -= i&-i\n",
    "        return res\n",
    "class Solution:\n",
    "    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        # 映射\n",
    "        p = [0]*n\n",
    "        for i,v in enumerate(nums1):\n",
    "            p[v] = i\n",
    "\n",
    "        # 计算左侧比它小的less\n",
    "        bit = BIT(n)\n",
    "        ans = 0\n",
    "        for i,v in enumerate(nums2):\n",
    "            value = p[v]\n",
    "            less = bit.count(value)\n",
    "            ans += less*(n-value-1-i+less)\n",
    "            bit.add(value+1,1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        # from sortedcontainers import SortedList\n",
    "        n = len(nums1)\n",
    "        numMap = [0]*n\n",
    "        for i, v in enumerate(nums1):\n",
    "            numMap[v] = i\n",
    "        # passed = SortedList()\n",
    "        result = 0\n",
    "        tree = [0]*(n+1)\n",
    "        for handled, x in enumerate(nums2):\n",
    "            v = numMap[x] + 1\n",
    "            j = v\n",
    "            # less = passed.bisect_left(v)\n",
    "            less = 0\n",
    "            while j:\n",
    "                less += tree[j]\n",
    "                j = j & (j-1)\n",
    "            more = handled - less\n",
    "            # passed.add(v)\n",
    "            j = v\n",
    "            while j <= n:\n",
    "                tree[j] += 1\n",
    "                j += j & -j\n",
    "            # handled: less  +    more \n",
    "            # unhandled(n-1-handled): v-1-less + x\n",
    "            # x = n-1-handled - (v-1-less) = n - handled - v + less\n",
    "            result += less*(n-handled -v + less)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#统计数组中好三元组数目,输入：nums1 = [2,0,1,3], nums2 = [0,1,2,3]输出：1;输入：nums1 = [4,0,1,3,2], nums2 = [4,1,0,2,3]输出：4\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        p = [0] * n\n",
    "        for i, x in enumerate(nums1):p[x] = i\n",
    "        ans = 0\n",
    "        s = SortedList()\n",
    "        for i in range(1, n - 1):\n",
    "            s.add(p[nums2[i - 1]])\n",
    "            y = p[nums2[i]]\n",
    "            less = s.bisect_left(y)\n",
    "            ans += less * (n - 1 - y - (i - less))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        res = 0\n",
    "        n = len(nums1)\n",
    "        pos = [0]*n\n",
    "        for i,x in enumerate(nums1):\n",
    "            pos[x] = i\n",
    "        tree = [0]*(n+1)\n",
    "        for i in range(n):\n",
    "            cur = pos[nums2[i]]\n",
    "            less = 0\n",
    "            while cur > 0:\n",
    "                less += tree[cur]\n",
    "                cur -= cur&-cur\n",
    "            res += less*(n-i-1-(pos[nums2[i]]-less))\n",
    "            cur = pos[nums2[i]]+1\n",
    "            while cur <= n:\n",
    "                tree[cur] += 1\n",
    "                cur += cur&-cur\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self,n):\n",
    "        self.tree=[0]*n\n",
    "    def add(self,x,val):\n",
    "        while x<len(self.tree):\n",
    "            self.tree[x]+=val\n",
    "            x+= x&-x\n",
    "    def query(self,x):\n",
    "        # if x==-1:\n",
    "        #     return 0\n",
    "        res=0\n",
    "        while x>0:\n",
    "            res+=self.tree[x]\n",
    "            x-=x&-x\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        p = [0] * n\n",
    "        for i, x in enumerate(nums1):\n",
    "            p[x] = i\n",
    "        res = 0\n",
    "        t=BIT(n)\n",
    "        for i in range(n):\n",
    "            num=p[nums2[i]]+1\n",
    "            q=t.query(num-1)\n",
    "            res+=q*(n-num-(i-q))\n",
    "            t.add(num,1)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self,n):\n",
    "        self.tree=[0]*n\n",
    "    def add(self,x,val):\n",
    "        while x<len(self.tree):\n",
    "            self.tree[x]+=val\n",
    "            x+= x&-x\n",
    "    def query(self,x):\n",
    "        # if x==-1:\n",
    "        #     return 0\n",
    "        res=0\n",
    "        while x>0:\n",
    "            res+=self.tree[x]\n",
    "            x-=x&-x\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        p = [0] * n\n",
    "        for i, x in enumerate(nums1):\n",
    "            p[x] = i\n",
    "        res = 0\n",
    "        t=BIT(n+1)\n",
    "        for i in range(n):\n",
    "            num=p[nums2[i]]+1\n",
    "            q=t.query(num-1)\n",
    "            res+=q*(n-num-(i-q))\n",
    "            t.add(num,1)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        p = [0] * n\n",
    "        for i, x in enumerate(nums1):\n",
    "            p[x] = i\n",
    "        ans = 0\n",
    "        tree = [0] * (n + 1)\n",
    "        for i in range(1, n - 1):\n",
    "            # 将 p[nums2[i - 1]] + 1 加入树状数组\n",
    "            j = p[nums2[i - 1]] + 1\n",
    "            while j <= n:\n",
    "                tree[j] += 1\n",
    "                j += j & -j\n",
    "            # 计算 less\n",
    "            y, less = p[nums2[i]], 0\n",
    "            j = y\n",
    "            while j:\n",
    "                less += tree[j]\n",
    "                j &= j - 1\n",
    "            ans += less * (n - 1 - y - (i - less))\n",
    "        return ans\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/count-good-triplets-in-an-array/solutions/1277695/deng-jie-zhuan-huan-shu-zhuang-shu-zu-by-xmyd/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict\n",
    "import random\n",
    "import copy\n",
    "import sys\n",
    "\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "\n",
    "class FenwickTree:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.sum_seg = [0] * (self.n + 1)\n",
    "\n",
    "    def __get_sum_with_end(self, end):\n",
    "        ans = 0\n",
    "        while end:\n",
    "            ans += self.sum_seg[end]\n",
    "            end &= (end - 1)\n",
    "        return ans\n",
    "\n",
    "    def get_sum(self, start, end):\n",
    "        start, end = start + 1, end + 1\n",
    "        if not (end >= start and start >= 1 and end <= self.n):\n",
    "            raise IndexError(f'bad range {(start - 1, end - 1)}')\n",
    "\n",
    "        if start == 1:\n",
    "            return self.__get_sum_with_end(end)\n",
    "        return self.__get_sum_with_end(end) - self.__get_sum_with_end(start - 1)\n",
    "\n",
    "    def add_val(self, x, delta):\n",
    "        x += 1\n",
    "        while x <= self.n:\n",
    "            self.sum_seg[x] += delta\n",
    "            x += x & (-x)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        pos1 = [0] * n\n",
    "        for i in range(n):\n",
    "            pos1[nums1[i]] = i\n",
    "\n",
    "        arr = []\n",
    "        for v in nums2:\n",
    "            arr.append(pos1[v])\n",
    "\n",
    "        tree = FenwickTree(n + 5)\n",
    "        tree.add_val(arr[0], 1)\n",
    "        tot = 0\n",
    "        for i in range(1, n):\n",
    "            A = tree.get_sum(0, arr[i])  # A是比arr[i]小的个数\n",
    "            tot += A * ((n - (i + 1)) - (arr[i] - A))\n",
    "            tree.add_val(arr[i], 1)\n",
    "        return tot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        d = {}\n",
    "        for i in range(n):\n",
    "            d[nums1[i]] = i\n",
    "        fen = [0] * (n+1)\n",
    "        def add(i):\n",
    "            while i <= n:\n",
    "                fen[i] += 1\n",
    "                i += i&-i\n",
    "        def query(i):\n",
    "            a = 0\n",
    "            while i:\n",
    "                a += fen[i]\n",
    "                i -= i&-i\n",
    "            return a\n",
    "        ans = 0\n",
    "        for i in range(1,n-1):\n",
    "            add(d[nums2[i - 1]] + 1)\n",
    "            p = d[nums2[i]]\n",
    "            t = query(p)      \n",
    "            ans += t * (n - i - p + t - 1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        # 长度为n的[0,n]的全排列数组两个，三个不同的值在两个数组中的出现位置相同的三元组\n",
    "        \n",
    "        # 转换为计算y的左侧有多少个比y小的树，右侧有多少个比y大的数\n",
    "        n = len(nums1)\n",
    "        pos = {num: i for i, num in enumerate(nums2)}\n",
    "        ans = 0\n",
    "        b = BIT(n + 1)\n",
    "        for i, num in enumerate(nums1):\n",
    "            j = pos[num]\n",
    "            left = b.query(j) # 找到元素位置\n",
    "            ans += left * (n - 1 - (i + j) + left)\n",
    "            b.add(j + 1, 1) # 将nums2的元素加入树状数组\n",
    "        return ans\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n:int):\n",
    "        self.tree = [0] * n\n",
    "    def add(self, i:int, v:int):\n",
    "        while i < len(self.tree):\n",
    "            self.tree[i] += v\n",
    "            i += i & -i\n",
    "    def query(self, i:int)-> int:\n",
    "        ans = 0\n",
    "        while i > 0:\n",
    "            ans += self.tree[i]\n",
    "            i -= (i & -i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        d = {}\n",
    "        for i in range(n):\n",
    "            d[nums1[i]] = i\n",
    "        fen = [0] * (n+1)\n",
    "        def add(i):\n",
    "            while i <= n:\n",
    "                fen[i] += 1\n",
    "                i += i&-i\n",
    "        def query(i):\n",
    "            a = 0\n",
    "            while i:\n",
    "                a += fen[i]\n",
    "                i -= i&-i\n",
    "            return a\n",
    "        ans = 0\n",
    "        for i in range(1,n-1):\n",
    "            add(d[nums2[i - 1]] + 1)\n",
    "            p = d[nums2[i]]\n",
    "            t = query(p)      \n",
    "            ans += t * (n - i - p + t - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.array = [0] * (n + 1)\n",
    "    \n",
    "    def update(self, idx):\n",
    "        idx += 1 \n",
    "        while idx < len(self.array):\n",
    "            self.array[idx] += 1 \n",
    "            idx += idx & (- idx)\n",
    "    \n",
    "    def query(self, idx):\n",
    "        res = 0\n",
    "        idx += 1 \n",
    "        while idx > 0:\n",
    "            res += self.array[idx]\n",
    "            idx -= idx & (- idx)\n",
    "        return res \n",
    "        \n",
    "\n",
    "class Solution:\n",
    "    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        dic = {}\n",
    "        for i in range(n):\n",
    "            dic[nums1[i]] = i \n",
    "        bit = BIT(n)\n",
    "        res = 0\n",
    "        for i, num in enumerate(nums2):\n",
    "            p = dic[num]\n",
    "            pre = bit.query(p - 1)\n",
    "            last = n - 1 - p - (i - pre)\n",
    "            res += pre * last \n",
    "            bit.update(p)\n",
    "        return res \n",
    "\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        d = {e:i for i,e in enumerate(nums1)}\n",
    "        ans = 0\n",
    "        n = len(nums1)\n",
    "        tree = BIT(n)\n",
    "        for i in range(1,n - 1):\n",
    "            tree.add(d[nums2[i - 1]] + 1,1)\n",
    "            y,less = d[nums2[i]],tree.query(d[nums2[i]])\n",
    "            ans += less*(n - 1 - y - (i - less))\n",
    "        return ans\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self,n):\n",
    "        self.tree = [0]*(n + 1)\n",
    "    \n",
    "    def add(self,i,v):\n",
    "        while i < len(self.tree):\n",
    "            self.tree[i] += v\n",
    "            i += i & -i\n",
    "    \n",
    "    def query(self,i):\n",
    "        ans = 0\n",
    "        while i:\n",
    "            ans += self.tree[i]\n",
    "            i &= i - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        p = {num: i + 1 for i, num in enumerate(nums1)}\n",
    "        n = len(nums1)\n",
    "        tree = [0] * (n + 1)\n",
    "\n",
    "        lowbit = lambda x : (x & -x)\n",
    "\n",
    "        def update(x):\n",
    "            while x < n + 1:\n",
    "                tree[x] += 1\n",
    "                x += lowbit(x)\n",
    "\n",
    "        def query(x):\n",
    "            ans = 0\n",
    "            while x:\n",
    "                ans += tree[x]\n",
    "                x -= lowbit(x)\n",
    "            return ans\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(1, n - 1):\n",
    "            update(p[nums2[i - 1]])\n",
    "            t = p[nums2[i]]\n",
    "            c = query(t)\n",
    "            ans += c * (n - i - t + c)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        mapping = {}\n",
    "        for i in range(n):\n",
    "            mapping[nums1[i]] = i + 1\n",
    "        nums = [mapping[num] for num in nums2]\n",
    "        dp = [0]*(n+1)\n",
    "        def lowbit(i):\n",
    "            return i & -i \n",
    "        def add(x):\n",
    "            i = x \n",
    "            while(i <= n):\n",
    "                dp[i] += 1\n",
    "                i += lowbit(i)\n",
    "            return\n",
    "        def subsum(x):\n",
    "            r = 0\n",
    "            i = x\n",
    "            while(i > 0):\n",
    "                r += dp[i]\n",
    "                i -= lowbit(i)\n",
    "            return r \n",
    "        result = 0\n",
    "        for i in range(n):\n",
    "            x = nums[i]\n",
    "            small = subsum(x)\n",
    "            big = (n-x)-(i-small)\n",
    "            result += small * big \n",
    "            add(x)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MAXN=10**5+10\n",
    "c=[0]*MAXN\n",
    "d=[0]*MAXN\n",
    "n=0\n",
    "lowbit=lambda x:x&-x\n",
    "def clear():\n",
    "    global n\n",
    "    for i in range(n+1):\n",
    "        c[i]=0\n",
    "        d[i]=0\n",
    "def query(c,i):\n",
    "    res=0\n",
    "    while i:\n",
    "        res+=c[i]\n",
    "        i-=lowbit(i)\n",
    "    return res\n",
    "def update(c,i,k):\n",
    "    global n\n",
    "    while i<=n:\n",
    "        c[i]+=k\n",
    "        i+=lowbit(i)\n",
    "\n",
    "class Solution:\n",
    "    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        global n\n",
    "        n=len(nums1)\n",
    "        mp1=[0]*n\n",
    "        mp2=[0]*n\n",
    "        clear()\n",
    "        for i in range(n):\n",
    "            mp1[nums1[i]]=i\n",
    "            mp2[nums2[i]]=i\n",
    "        nums=list(zip(mp1,mp2))\n",
    "        nums.sort()\n",
    "        for _,x in nums:\n",
    "            update(d,x+1,1)\n",
    "        res=0\n",
    "        for _,x in nums:\n",
    "            x+=1\n",
    "            update(d,x,-1)\n",
    "            res+=query(c,x-1)*(query(d,n)-query(d,x))\n",
    "           # print(x,query(c,x-1),query(d,x))\n",
    "            update(c,x,1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        p = {num: i + 1 for i, num in enumerate(nums1)}\n",
    "        n = len(nums1)\n",
    "        tree = [0] * (n + 1)\n",
    "        lowbit = lambda x : (x & -x)\n",
    "\n",
    "        def update(x):\n",
    "            while x < n + 1:\n",
    "                tree[x] += 1\n",
    "                x += lowbit(x)\n",
    "\n",
    "        def query(x):\n",
    "            total = 0\n",
    "            while x:\n",
    "                total += tree[x]\n",
    "                x -= lowbit(x)\n",
    "            return total\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(1, n - 1):\n",
    "            num = p[nums2[i]]\n",
    "            pre = p[nums2[i - 1]]\n",
    "            update(pre)\n",
    "            t = query(num)\n",
    "            ans += t * (n - num - i + t)\n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MAXN=10**5+10\n",
    "c=[0]*MAXN\n",
    "d=[0]*MAXN\n",
    "n=0\n",
    "lowbit=lambda x:x&-x\n",
    "def clear():\n",
    "    global n\n",
    "    for i in range(n+1):\n",
    "        c[i]=0\n",
    "        d[i]=0\n",
    "def query(c,i):\n",
    "    res=0\n",
    "    while i:\n",
    "        res+=c[i]\n",
    "        i-=lowbit(i)\n",
    "    return res\n",
    "def update(c,i,k):\n",
    "    global n\n",
    "    while i<=n:\n",
    "        c[i]+=k\n",
    "        i+=lowbit(i)\n",
    "\n",
    "class Solution:\n",
    "    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        global n\n",
    "        n=len(nums1)\n",
    "        mp1=[0]*n\n",
    "        mp2=[0]*n\n",
    "        clear()\n",
    "        for i in range(n):\n",
    "            mp1[nums1[i]]=i\n",
    "            mp2[nums2[i]]=i\n",
    "        nums=list(zip(mp1,mp2))\n",
    "        nums.sort()\n",
    "        for _,x in nums:\n",
    "            update(d,x+1,1)\n",
    "        res=0\n",
    "        for _,x in nums:\n",
    "            x+=1\n",
    "            update(d,x,-1)\n",
    "            res+=query(c,x-1)*(query(d,n)-query(d,x))\n",
    "            update(c,x,1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class FenwickTree:\n",
    "    def __init__(self, n):\n",
    "        self.size = n\n",
    "        self.tree = [0] * (n + 1)\n",
    "\n",
    "    # 将下标 i 上的数加一\n",
    "    def inc(self, i: int) -> None:\n",
    "        while i < len(self.tree):\n",
    "            self.tree[i] += 1\n",
    "            i += i & -i\n",
    "\n",
    "    # 返回闭区间 [1, i] 的元素和\n",
    "    def sum(self, i: int) -> int:\n",
    "        res = 0\n",
    "        while i > 0:\n",
    "            res += self.tree[i]\n",
    "            i &= i - 1\n",
    "        return res\n",
    "\n",
    "    # 返回闭区间 [left, right] 的元素和\n",
    "    def query(self, left: int, right: int) -> int:\n",
    "        return self.sum(right) - self.sum(left - 1)\n",
    "    \n",
    "class Solution:\n",
    "    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        idx = defaultdict(int)\n",
    "        for i, c in enumerate(nums2):\n",
    "            idx[c] = i + 1\n",
    "        n = len(nums1)\n",
    "        ft = FenwickTree(n)\n",
    "        ans = 0\n",
    "        for x in nums1:\n",
    "            j = idx[x]\n",
    "            ft.inc(j)\n",
    "            ans += ft.query(1, j-1) * (n - j - ft.query(j+1, n))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.array = [0] * (n + 1)\n",
    "    \n",
    "    def update(self, idx):\n",
    "        idx += 1 \n",
    "        while idx < len(self.array):\n",
    "            self.array[idx] += 1 \n",
    "            idx += idx & (- idx)\n",
    "    \n",
    "    def query(self, idx):\n",
    "        res = 0\n",
    "        idx += 1 \n",
    "        while idx > 0:\n",
    "            res += self.array[idx]\n",
    "            idx -= idx & (- idx)\n",
    "        return res \n",
    "        \n",
    "\n",
    "class Solution:\n",
    "    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        dic = {}\n",
    "        for i in range(n):\n",
    "            dic[nums1[i]] = i \n",
    "        bit = BIT(n)\n",
    "        res = 0\n",
    "        for i, num in enumerate(nums2):\n",
    "            p = dic[num]\n",
    "            pre = bit.query(p - 1)\n",
    "            last = n - 1 - p - (i - pre)\n",
    "            res += pre * last \n",
    "            bit.update(p)\n",
    "        return res \n",
    "\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        # print(help(bisect))\n",
    "        n = len(nums1)\n",
    "        idx1Map = {x:i for i, x in enumerate(nums1)}\n",
    "        nums = [idx1Map[x] for x in nums2] # num1在nums2中的索引映射\n",
    "        leftIdxNums = [nums[0]]\n",
    "        ans = 0\n",
    "        for i in range(1, n-1):\n",
    "            idx1 = nums[i]\n",
    "            bisect.insort(leftIdxNums, idx1) # 维护当前索引位置nums1左侧的索引\n",
    "            # print(f\"leftIdxNums:{leftIdxNums}\")\n",
    "            l = bisect.bisect_left(leftIdxNums, idx1)\n",
    "            r = n - 1 - idx1 - (i - l)\n",
    "            ans += l * r\n",
    "        return ans\n",
    "    def goodTriplets2(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        idx2Map = {x:i for i, x in enumerate(nums2)}\n",
    "        ans, n = 0, len(nums1)\n",
    "        for i in range(n-2):\n",
    "            x = idx2Map[nums1[i]]\n",
    "            if x >= n - 2:\n",
    "                continue\n",
    "            for j in range(i+1, n-1):\n",
    "                y = idx2Map[nums1[j]]\n",
    "                if y < x:\n",
    "                    continue\n",
    "                if y >= n - 1:\n",
    "                    continue\n",
    "                for k in range(j+1, n):\n",
    "                    z = idx2Map[nums1[k]]\n",
    "                    if z > y:\n",
    "                        ans += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        d = {e:i for i,e in enumerate(nums1)}\n",
    "        nums2 = [d[x] for x in nums2]\n",
    "        tree = BIT(n)\n",
    "        ans = 0\n",
    "        for i,x in enumerate(nums2):\n",
    "            less = tree.query(x)\n",
    "            # x 范围[0,n -1]\n",
    "            ans += less * (n - 1 - x -  (i - less))\n",
    "            tree.add(x + 1,1)\n",
    "        return ans\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self,n):\n",
    "        self.tree = [0]*(n + 1)\n",
    "\n",
    "    def add(self,i,v):\n",
    "        while i < len(self.tree):\n",
    "            self.tree[i] += v\n",
    "            i += i & -i\n",
    "    \n",
    "    def query(self,i):\n",
    "        ans = 0\n",
    "        while i > 0:\n",
    "            ans += self.tree[i]\n",
    "            i &= i - 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n, idx_map = len(nums1), {num:i for i, num in enumerate(nums1)}\n",
    "        for i in range(n):\n",
    "            nums2[i] = idx_map[nums2[i]]\n",
    "        sl, ans = SortedList(), 0\n",
    "        for i in nums2:\n",
    "            idx = sl.bisect_left(i)\n",
    "            ans += idx * (n - 1 - i - len(sl) + idx)\n",
    "            sl.add(i)\n",
    "        return ans\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        tree = [0] * (n+1)\n",
    "        def lowbit(x):\n",
    "            return x & -x\n",
    "        def add(pos):\n",
    "            while(pos<=n):\n",
    "                # print(pos)\n",
    "                tree[pos]+=1\n",
    "                pos+=lowbit(pos)\n",
    "        def query(pos):\n",
    "            ret = 0\n",
    "            while(pos>0):\n",
    "                # print(pos)\n",
    "                ret += tree[pos]\n",
    "                pos -= lowbit(pos)\n",
    "            return ret\n",
    "        pos = [0]*n\n",
    "        for i in range(n):\n",
    "            pos[nums2[i]] = i\n",
    "        \n",
    "        f = [0] * (n+1)\n",
    "        g = [0] * (n+1)\n",
    "\n",
    "        for i in range(n):\n",
    "            f[i+1] = query(pos[nums1[i]] + 1)\n",
    "            add(pos[nums1[i]] + 1)\n",
    "            \n",
    "        # print(f)\n",
    "\n",
    "        tree = [0] * (n+1)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            # print(i, n-pos[nums1[i]])\n",
    "            g[i+1] = query(n-pos[nums1[i]])\n",
    "            add(n - pos[nums1[i]])\n",
    "            \n",
    "        # print(g)\n",
    "        ans = 0\n",
    "        for i in range(1,n+1):\n",
    "            ans+=f[i] * g[i]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n=len(nums1)\n",
    "        from sortedcontainers import SortedList\n",
    "        sd=SortedList()\n",
    "\n",
    "        dic={v:i for i,v in enumerate(nums2)}\n",
    "\n",
    "        res=0\n",
    "        for i,v in enumerate(nums1):\n",
    "            j=dic[v]\n",
    "            if sd:\n",
    "                L=sd.bisect_left(j)\n",
    "                R=n-j-1-(i-L)\n",
    "                res+=L*R\n",
    "            sd.add(j)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self,n):\n",
    "        self.F = [0] * n \n",
    "        self.n = n\n",
    "        \n",
    "    def update(self,pos):\n",
    "        while pos < self.n:\n",
    "            self.F[pos] += 1\n",
    "            pos += pos & -pos\n",
    "    \n",
    "    def query(self,pos):\n",
    "        res = 0\n",
    "        while pos:\n",
    "            res += self.F[pos]\n",
    "            pos -= pos & -pos\n",
    "        return res\n",
    "class Solution:\n",
    "    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        L = [0] * n\n",
    "        D = {}\n",
    "        for idx,i in enumerate(nums2):\n",
    "            D[i] = idx\n",
    "        for idx,i in enumerate(nums1):\n",
    "            L[idx] = D[i]\n",
    "        Tr = BIT(n+1)\n",
    "        res = 0\n",
    "        for idx,i in enumerate(L):\n",
    "            if idx:\n",
    "                v = Tr.query(i)\n",
    "                res += (n-1-i-(idx-v)) * v\n",
    "            Tr.update(i+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def goodTriplets(self, a: List[int], b: List[int]) -> int:\n",
    "        c = {a[j]:j for j in range(len(a))} \n",
    "        b = [c[j] for j in b]\n",
    "        a = SortedList([])\n",
    "        c = SortedList(b[1:])\n",
    "        ans = 0\n",
    "        for j in range(len(b))[1:]:\n",
    "            a.add(b[j - 1])\n",
    "            c.remove(b[j])\n",
    "            ans += a.bisect_left(b[j])*(len(c) - c.bisect_right(b[j]))\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BinaryIndexTree:\n",
    "\n",
    "    def __init__(self, array: list):\n",
    "        '''初始化，总时间 O(n)'''\n",
    "        self._array = [0] + array\n",
    "        n = len(array)\n",
    "        for i in range(1, n + 1):\n",
    "            j = i + (i & -i)\n",
    "            if j < n + 1:\n",
    "                self._array[j] += self._array[i]\n",
    "\n",
    "    def lowbit(self, x: int) -> int:\n",
    "        return x & (-x)\n",
    "\n",
    "    def update(self, idx: int, val: int):\n",
    "\n",
    "        prev = self.query(idx, idx + 1)    # 计算出原来的值\n",
    "        idx += 1\n",
    "        val -= prev    # val 是要增加的值\n",
    "        while idx < len(self._array):\n",
    "            self._array[idx] += val\n",
    "            idx += self.lowbit(idx)\n",
    "\n",
    "    def query(self, begin: int, end: int) -> int:\n",
    "        '''返回数组[begin, end) 的和'''\n",
    "        return self._query(end) - self._query(begin)\n",
    "\n",
    "    def _query(self, idx: int) -> int:\n",
    "        '''计算数组[0, idx)的元素之和'''\n",
    "        res = 0\n",
    "        while idx > 0:\n",
    "            res += self._array[idx]\n",
    "            idx -= self.lowbit(idx)\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        id = {}\n",
    "        n = len(nums1)\n",
    "        for i in range(n):\n",
    "            id[nums1[i]] = i\n",
    "        nums2 = [id[c] for c in nums2]\n",
    "        bt = BinaryIndexTree([0 for _ in range(n + 1)])\n",
    "        ans = 0\n",
    "        ldp = []\n",
    "        for i in range(n):\n",
    "            cur = nums2[i]\n",
    "            left = bt._query(cur)\n",
    "            ldp.append(left)\n",
    "            bt.update(cur,1)\n",
    "        rdp = []\n",
    "        for i in range(n + 1):\n",
    "            bt.update(i,0)\n",
    "        for i in range(n - 1,-1,-1):\n",
    "            cur = nums2[i]\n",
    "            right = bt.query(cur + 1,n)\n",
    "            rdp.append(right)\n",
    "            bt.update(cur,1)\n",
    "        rdp = rdp[::-1]\n",
    "        for i in range(n):\n",
    "            ans += ldp[i] * rdp[i]\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, nums): # init BIT\n",
    "        self.tree = [0] + nums\n",
    "        for i in range(1, len(self.tree)):\n",
    "            p = i + (i & -i) # index to parent\n",
    "            if p < len(self.tree):\n",
    "                self.tree[p] += self.tree[i]\n",
    "\n",
    "    def add(self, i, k): # add k to index i\n",
    "        while i < len(self.tree):\n",
    "            self.tree[i] += k\n",
    "            i += (i & -i) # add last set bit\n",
    "\n",
    "    def sum(self, i): # sum from index 1 to i\n",
    "        res = 0\n",
    "        while i > 0:\n",
    "            res += self.tree[i]\n",
    "            i -= (i & -i) # minus the last set bit\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        bit1, bit2 = BIT([0] * n), BIT([0] * n)\n",
    "        d = {v: i for i, v in enumerate(nums1)} # map\n",
    "        prefix, suffix = [0] * n, [0] * n\n",
    "        for i in range(1, n - 1):\n",
    "            bit1.add(d[nums2[i - 1]] + 1, 1)\n",
    "            s = bit1.sum(d[nums2[i]] + 1)\n",
    "            prefix[i] = s\n",
    "        for i in range(n - 2, 0, -1):\n",
    "            bit2.add(d[nums2[i + 1]] + 1, 1)\n",
    "            s = bit2.sum(n) - bit2.sum(d[nums2[i]] + 1)\n",
    "            suffix[i] = s\n",
    "        res = 0\n",
    "        for a, b in zip(prefix, suffix):\n",
    "            res += a * b\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, nums): # init BIT\n",
    "        self.tree = [0] + nums\n",
    "        for i in range(1, len(self.tree)):\n",
    "            p = i + (i & -i) # index to parent\n",
    "            if p < len(self.tree):\n",
    "                self.tree[p] += self.tree[i]\n",
    "\n",
    "    def add(self, i, k): # add k to index i\n",
    "        while i < len(self.tree):\n",
    "            self.tree[i] += k\n",
    "            i += (i & -i) # add last set bit\n",
    "\n",
    "    def sum(self, i): # sum from index 1 to i\n",
    "        res = 0\n",
    "        while i > 0:\n",
    "            res += self.tree[i]\n",
    "            i -= (i & -i) # minus the last set bit\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        bit1, bit2 = BIT([0] * n), BIT([0] * n)\n",
    "        d = {v: i for i, v in enumerate(nums1)} # map\n",
    "        prefix, suffix = [0] * n, [0] * n\n",
    "        for i in range(1, n - 1):\n",
    "            bit1.add(d[nums2[i - 1]] + 1, 1)\n",
    "            s = bit1.sum(d[nums2[i]] + 1)\n",
    "            prefix[i] = s\n",
    "        for i in range(n - 2, 0, -1):\n",
    "            bit2.add(d[nums2[i + 1]] + 1, 1)\n",
    "            s = bit2.sum(n) - bit2.sum(d[nums2[i]] + 1)\n",
    "            suffix[i] = s\n",
    "        res = 0\n",
    "        for a, b in zip(prefix, suffix):\n",
    "            res += a * b\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
